// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-26 20:07
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.GraphyTrain;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;

import java.util.*;

public class ZigZagLevelOrder {
    // 锯齿形层次遍历树节点
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 朴素遍历方法，
        // 两个队列交替使用，p队列输出的列表不需要进行逆序，q队列的列表需要进行逆序
        Queue<TreeNode> p = new LinkedList<>();
        Queue<TreeNode> q = new LinkedList<>();
        Stack<Integer> qStack = new Stack<>(); // 用于对q输出的数据进行逆序操作

        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        p.offer(root);
        while (!p.isEmpty() || !q.isEmpty()) {
            ArrayList<Integer> ql = new ArrayList<>();
            ArrayList<Integer> pl = new ArrayList<>();
            while (!p.isEmpty()) { // p队列的输出不需要进行逆序操作
                TreeNode t = p.poll();
                if (t.left != null) {
                    q.offer(t.left);
                }
                if (t.right != null) {
                    q.offer(t.right);
                }
                pl.add(t.val);
            }
            if (!pl.isEmpty()) {
                res.add(pl);
            }
            while (!q.isEmpty()) { // q队列的输出列表需要进行逆序操作，使用中间栈实现对列表的逆序操作
                TreeNode qt = q.poll();
                if (qt.left != null) {
                    p.offer(qt.left);
                }
                if (qt.right != null) {
                    p.offer(qt.right);
                }
                // 入栈
                qStack.push(qt.val);
            }

            // 取栈
            while (!qStack.isEmpty()) {
                ql.add(qStack.pop());
            }

            if (!ql.isEmpty()) {
                res.add(ql);
            }
        }
        return res;
    }


}

